This invention relates generally to data routing systems and more specifically to data packet routing systems over multiple physical links.
The following paragraphs give definitions of terms used throughout this document.
Physical link: a single point-to-point (PPP) serial transmission link between two nodes in the network (such as between two routers or between a router and a host machine). The implementation of a serial link may take various forms such as an optical fibre or a wavelength segment on an optical fibre, among other options.
Physical input/output port: the input/output port of the router that supports one physical link.
Logical link: a point-to-point traffic path between two routers that is composed of multiple physical links and appears from a routing point of view to be one link.
Logical input/output port: the collection of physical input/output ports that support the physical links of a logical link.
Supertrunk: the aggregation of physical links into larger, logical links.
Transmission Control Protocol (TCP): a library of routines that applications can use when they need reliable network communications with another computer. TCP is responsible for verifying the correct delivery of data from client to server. It adds support to detect errors or lost data and to trigger reconstruction until the data is correctly and completely received.
Internet Protocol (IP): a library of routines that TCP calls on, but which is also available to applications that do not use TCP. IP is responsible for transporting packets of data from node to node. It forwards each packet based on a four-byte destination address (the IP address).
There has been an incredible increase in demand for bandwidth within communication routing systems over the past few years. This increase is particularly pronounced when considering the increase in data networking information transferred within these systems directly associated with the expanding popularity of the Internet. Soon the traffic rates needed between router pairs will be higher than the serial link transmission technology available. Currently, the highest transmission rate is 9.6 Gb/s, (on a single wavelength) but 2.4 Gb/s is much more commonly available. Purchasers of routers are already demanding 2.4 Gb/s links and it is expected that within a short time, some routes will require multiple physical links.
There are other reasons why multi-link routes are attractive. In situations where routers are clustered in close physical proximity, the use of multiple links might allow the interconnect to be multiple low cost links rather than single high cost connections. Another reason is that the application of the multi-link approach might also be a fast way to provide higher rate ports on existing routers. Yet another reason is that the use of multiple links allows more granularity of growth than the large steps in the transmission network and so may allow savings in bandwidth costs. Finally, another reason is that multiple links can allow for redundancy to cover link failure without requiring the spare link to cover the whole bandwidth of the route.
When using multiple links between two routers, it is a requirement that the total bandwidth be used efficiently. That is to say, the traffic offered must be spread over all available links, hereinafter referred to as load balancing. It would not be acceptable to have one link under utilized while traffic is queued on another. This suggests that packets from any source can be delivered over any link to any destination. In fact, because of the bursting nature of the traffic, allocating links statically to particular sources or destinations would result in inefficient use of the total available bandwidth.
When traffic streams are spread over multiple links, successive packets from a particular flow (for example, a TCP connection between two IP hosts) can travel over different lengths and may arrive at the destination out of order. The variability of delay can be caused by different path lengths or different congestion levels on the paths, as well as the normal indeterminacy introduced by queuing and scheduling. The TCP can accommodate some mis-ordering of packets, but there is a problem if too much mis-ordering occurs on a connection where the transmitter is using the fast retransmission protocol.
Therefore, when utilizing a supertrunk to transfer data between two routers, it is important to establish a routing system that comprises both an efficient load balancing function to distribute the individual packets among the physical links and an effective sorting function to handle mis-ordered data packets. Another key consideration, is the compatibility of the protocol headers, corresponding to the data packets after having load balancing information attached, with the networks comprised within the physical links of a supertrunk. Each of the physical links of a supertrunk may be implemented with a series of connections within a series of networks with different protocols. The individual data packets traversing these physical links must have a header recognized by these different networks without modifications being required at the network level.
Hence, a general implementation of a routing system is required that supports supertrunks and, as a result, provides more efficient use of bandwidth within a series of physical links. This supertrunk routing system should not make significant changes to the overall operation of the current routing systems or networks within the physical links, but should allow individual IP packets from a single IP stream to be transferred from one router to another via different physical links.
It is an object of the present invention to overcome the disadvantages of the prior art and, in particular, to provide an apparatus and method for increasing the efficiency of data packet communications.
According to a first aspect, the present invention provides a forwarding node capable of operation within a router that transfers digital data with a plurality of other routers within a packet routing system, the forwarding node comprising: a load balancing device that, when input with individual packets of a data stream, reads a logical output port corresponding to the data stream, assigns each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria, encapsulates the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier, and outputs the packets to their assigned physical output ports; and a packet sorting device that, when input with encapsulated packets, re-orders the packets into the proper order with use of a sorting algorithm utilizing the packet sequence identifiers and outputs a data stream corresponding to the re-ordered packets.
According to a second aspect, the present invention provides a router capable of operation within a packet routing system that transfers digital data between a plurality of the routers, the router comprising: a route controller; a rotator space switch; at least one first forwarding node, coupled to both the route controller and the rotator space switch, comprising a load balancing device that, when input with individual packets of a data stream, reads a logical output port corresponding to the data stream, assigns each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria, encapsulates the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier, and outputs the packets to their assigned physical output ports; at least one second forwarding node, coupled to both the route controller and the rotator space switch, that is arranged to operate as a physical output port for outputting encapsulated packets to at least one transmission apparatus; at least one third forwarding node, coupled to both the route controller and the rotator space switch, that is arranged to operate as a physical input port for receiving encapsulated packets from at least one transmission apparatus; and at least one fourth forwarding node, coupled to both the route controller and the rotator space switch, comprising a packet sorting device that, when input with encapsulated packets, re-orders the packets into the proper order with use of a sorting algorithm utilizing the packet sequence identifiers and outputs a data stream corresponding to the re-ordered packets.
According to a third aspect, the present invention provides a packet routing system that transfers digital data between at least one first router and at least one second router, the packet routing system comprising: the first router comprising: a first route controller; a first rotator space switch; at least one first forwarding node, coupled to both the first route controller and the first rotator space switch, comprising a load balancing device that, when input with individual packets of a data stream, reads a logical output port corresponding to the data stream, assigns each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria, encapsulates the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier, and outputs the packets to their assigned physical output ports; at least one second forwarding node, coupled to both the first route controller and the first rotator space switch, that is arranged to operate as a physical output port for outputting encapsulated packets to at least one transmission apparatus; a plurality of transmission apparatuses coupled between the first and second routers; and the second router comprising: a second route controller; a second rotator space switch; at least one third forwarding node, coupled to both the second route controller and the second rotator space switch, that is arranged to operate as a physical input port for receiving encapsulated packets from at least one transmission apparatus; and at least one fourth forwarding node, coupled to both the second route controller and the second rotator space switch, comprising a packet sorting device that, when input with encapsulated packets, re-orders the packets into the proper order with use of a sorting algorithm utilizing the packet sequence identifiers and outputs a data stream corresponding to the re-ordered packets.
According to a fourth aspect, the present invention provides in a packet routing system comprising a plurality of routers, a method of transferring digital data between the routers comprising the steps of: inputting individual packets of a data stream into a first router; reading a logical output port corresponding to the data stream of the individual packets; assigning each of the individual packets of the data stream to a physical output port within the logical output port based upon physical link criteria; encapsulating each of the individual packets with a first routing header that comprises a data stream identifier, a packet sequence identifier, and a physical output port identifier corresponding to the assigned physical output port; transmitting each of the encapsulated packets, via their assigned physical output port, to a second router; re-ordering the resulting packets into the proper order with use of a sorting algorithm utilizing the packet sequence identifiers; and outputting a data stream corresponding to the re-ordered packets.